package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/5 23:13
 * @description：https://leetcode-cn.com/problems/number-of-atoms/
 */
public class 原子的数量 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.countOfAtoms("K4(ON(SO3)2)2"));
    }

    class Solution {
        public String countOfAtoms(String formula) {
            int len = formula.length();
            Map<String, Integer> map = new HashMap<>();
            List<String> list = new ArrayList<>();
            Stack<Integer> stack = new Stack<Integer>();
            char[] chars = formula.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char ch = chars[i];
                if (isUpLetter(ch)) {
                    String key = ch + "";
                    int num = 1;
                    if (i + 1 < len) {
                        if (isNum(chars[i + 1])) {
                            num = chars[++i] - '0';
                        } else if (isDownLetter(chars[i + 1])) {
                            key += chars[++i];
                        }
                    }
                    map.put(key + "", map.getOrDefault(key + "", 0) + num);
                    if (!list.contains(key)) list.add(key);
                    continue;
                } else if (ch == '(') {
                    stack.push(i);
                } else if (ch == ')') {
                    int index = stack.pop();
                    int num = 1;
                    if (i + 1 < len) {
                        if (isNum(chars[i + 1])) {
                            num = chars[++i] - '0';
                        }
                    }
                    for (int j = index + 1; j < i && isUpLetter(chars[j]); j++) {
                        ch = chars[j];
                        if (ch != '(' && ch != ')')
                            map.put(ch + "", map.getOrDefault(ch + "", 1) * num - 1);
                    }
                }
            }
            list.sort(String::compareTo);
            StringBuilder builder = new StringBuilder();
            for (String s : list) {
                builder.append(s);
                if (map.get(s) != 1)
                    builder.append(map.get(s));
            }
            return builder.toString();
        }
    }


    public boolean isUpLetter(char ch) {
        return (ch >= 'A' && ch <= 'Z');
    }

    public boolean isDownLetter(char ch) {
        return (ch >= 'a' && ch <= 'z');
    }

    public boolean isNum(char ch) {
        return ch >= '0' && ch <= '9';
    }
}
